The Fourier transform maps functions to other functions. Generally, the Fourier transform decomposes a function into a continuous spectrum of its frequency components. Likewise, the inverse Fourier transform synthesizes a function from its spectrum of frequency components. The discrete Fourier transform (DFT) is a transform for Fourier analysis of finite-domain discrete-time signals.
The DFT of a vector r of length N is defined as follows:
            y      k        =                            1                      N                          ⁢                              ∑                          n              =              0                                      N              -              1                                ⁢                                    ⅇ                                                -                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                      ⅈ                                        N                                                  ⁢                kn                                      ⁢                          r              n                        ⁢                                                  ⁢            where            ⁢                                                  ⁢            k                              =      0        ,  …  ⁢          ,      N    -    1.  See, for example, E. C. Ifeachor and B. W. Jervis, “Digital Signal Processing: A Practical Approach,” Addison-Wesley, June 1993; or http://en.wikipedia.org/wiki/Discerete_fourier_transform. Evaluating these sums directly would take on the order of N2 arithmetical operations. A fast Fourier transform (FFT) algorithm reduces the complexity to an order of N log N operations. In general, such algorithms depend upon the factorization of N, so for most values of N, the FFT complexity is on the order of N log N.
One popular FFT implementation is the Cooley-Tukey algorithm. Generally, the Cooley-Tukey algorithm recursively breaks down a DFT of any composite size N equal to N1·N2 into many smaller DFTs of sizes N1 and N2, along with order of N multiplications by complex toots of unity The most well-known use of the Cooley-Tukey algorithm divides the transform into two pieces of size N/2 at each step, and is therefore limited to power-of-two sizes. In general, however, any factorization can be used, such as radix-2 and mixed-radix algorithms.
While such existing FFT algorithms efficiently decompose a function of length N into a discrete spectrum of its frequency components for many values of N, brute force DFTs must still generally be used when N is a large prime number. A need therefore exists for improved methods and apparatus that approximate the DFT result for a large prime number.